package leetcode_900;

import java.util.TreeSet;

import helpclass.Point;

/**
 *@author 周杨
 *ExamRoom_855_ 实现一个数据结构 要求给定N个位置(N非常大 ) 调用两种方法 一种插入学生 一种删除学生 要求每次插入都要插入到一个位置到两边有位置下标的最小值
 *describe:用TreeSet排序区间 每次插入就取头的元素 并不断调整TreeSet AC 26%
 *2018年11月4日 下午4:34:13
 */
public class ExamRoom_855_ {
	private int N;
    private TreeSet<Integer> seats = new TreeSet<>();
    private TreeSet<Point> pq = new TreeSet<Point>(//Point表示区间[x,y]
            (Point p1, Point p2) -> {//声明排序规则
                int d1 = getDistance(p1);
                int d2 = getDistance(p2);
                if (d1 == d2) {//如果两区间的 区间隔间距离相同 那么看哪个lower
                    return p1.x - p2.x; 
                }
                return d2 - d1;//否则就取小区间
            });

    public ExamRoom_855_(int N) {
        this.N = N;
        seats.add(-1);
        seats.add(N);
        pq.add(new Point(-1, N));//增加最大区间
    }
    
    private int getDistance(Point p) {//获取一个区间离中间值的间隔
        int mid = getMid(p.x, p.y);//获取一个区间的 中间值
        if (p.x < 0) {
            return p.y - mid;
        } else if (p.y == this.N) {
            return mid - p.x;            
        }
        return Math.min(p.y - mid, mid - p.x);
    }
    
    private int getMid(int left, int right) {
        if (left < 0) return 0;
        if (right == this.N) return this.N - 1;
        return (left + right) / 2;
    }
    
    public int seat() {
        Point p = pq.pollFirst();//因为区间是按最小间隔排序的 那么第一个就是候选解
        int left = p.x, right = p.y;
        int mid = getMid(left, right);
        seats.add(mid);
        pq.add(new Point(left, mid));
        pq.add(new Point(mid, right));
        return mid;
    }
    
    public void leave(int p) {
        int left = seats.lower(p);
        int right = seats.higher(p);
        seats.remove(p);
        pq.remove(new Point(left, p));//删除以p所在的 两个区间
        pq.remove(new Point(p, right));
        pq.add(new Point(left, right));//重新扩充这个区间
    }
}
